package cn.hy.today;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution_2707 {
    public int minExtraChar(String s, String[] dictionary) {
        // 用hash 存储字符
        Set<String> set = new HashSet<>(Arrays.asList(dictionary));
        int n = s.length();
        // 把 s 的最后一个字符 s[n−1]当做是额外字符，那么问题转为长度为 n−1 的子问题
        // 找到一个 j 使得 sss 的后缀 s[j...n−1] 构成的子串在 dictionary，那么问题转为长度为 j−1的子问题。
        int[] d = new int[n + 1];
        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            // 把 s[i−1] 当做是额外字符，d[i]=d[i−1]+1
            d[i] = d[i - 1] + 1;
            // 遍历所有的 j(j∈[0,i−1])，如果子字符串 s[j...i−1] 存在于 dictionary 中，那么 d[i]= min d[j]
            for (int j = 0; j < i; j++) {
                if (set.contains(s.substring(j, i))) {
                    d[i] = Math.min(d[i], d[j]);
                }
            }
        }
        return d[n];
    }
}